package com.cwl.data.queue;

/**
 * @program: data-structure
 * @description: 队列
 * @author: ChenWenLong
 * @create: 2019-09-10 10:12
 **/
public class MyQueue<T> {

    // 队头
    private Node<T> front;
    // 队尾
    private Node<T> rear;
    // 元素个数
    private int size;

    //内部节点
    private class Node<T> {
        Node<T> next = null;// 节点的引用，指向下一个节点
        T data;// 节点的对象，即内容

        public Node(T data) {
            this.data = data;
        }
    }

    /**
     * 功能描述:
     * 〈创建一个空的队列〉
     *
     * @params : []
     * @return :
     * @author : cwl
     * @date : 2019/9/10 10:14
     */
    public MyQueue() {
        rear = front = null;
    }

    /**
     * 功能描述:
     * 〈入队列〉
     *
     * @params : [data]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:16
     */
    public void enQueue(T data) {
        Node<T> node = new Node<T>(data);
        if (isEmputy()) {
            front = rear = node;
        } else {
            rear.next= node;
            rear = node;
        }

        size++;
    }

    /**
     * 功能描述:
     * 〈出队列〉
     *
     * @params : []
     * @return : T
     * @author : cwl
     * @date : 2019/9/10 10:17
     */
    public T deQueue() {
        if (isEmputy()) {
            throw new RuntimeException("队列为空");
        }

        Node<T> delete = front;
        front = delete.next;
        delete.next = null;;
        size--;
        if (size == 0) {
            // 删除掉最后一个元素时，front值已经为null，但rear还是指向该节点，需要将rear置为null
            // 最后一个结点front和rear两个引用都没指向它，帮助GC处理该节点对象
            rear = front;
        }
        return delete.data;
    }

    /**
     * 功能描述:
     * 〈判断队列是否为空〉
     *
     * @params : []
     * @return : boolean
     * @author : cwl
     * @date : 2019/9/10 10:21
     */
    public boolean isEmputy() {
        return (front == null && rear == null) ? true : false;
    }

    /**
     * 功能描述:
     * 〈获取队列的元素个数〉
     *
     * @params : []
     * @return : int
     * @author : cwl
     * @date : 2019/9/10 10:22
     */
    public int size() {
        return this.size;
    }
}
